// 给定一个数组nums，找出数组排序之后，相邻元素之间最大的差值，如果数组元素个数小于2，则返回0
// 在时间复杂度和空间复杂度都为线性复杂度
// 所有元素都是非负整数，且数值在32位有符号整数范围内

// 思路：对时间和空间复杂度有要求，排序的话只能基数排序
function maximumGap(nums) {
    if (nums.length < 2) {
        return 0
    }
    let arr = radixSort(nums)
    let max = 0
    for (let i = 1; i < arr.length; i++) {
        if ((arr[i] - arr[i - 1]) > max) {
            max = arr[i] - arr[i - 1]
        }
    }
    return max
}

function radixSort(nums) {
    // 这里注意Math.max方法传入数组必须解构下呀
    let size = String(Math.max(...nums)).length
    for (let i = 0; i <= size; i++) {
        let buckets = new Array(10).fill(1).map(_ => [])
        for (let j = 0; j < nums.length; j++) {
            let index = Math.floor(nums[j] / Math.pow(10, i)) % 10
            buckets[index].push(nums[j])
        }
        nums = []
        for (let j = 0; j < buckets.length; j++) {
            nums = nums.concat(buckets[j])
        }
    }
    return nums
}

let arr = [3, 65, 98, 1]
let nums =
[1,10000000]
// console.log(maximumGap(arr));
console.log(maximumGap(nums));
